class Solution {
public:
    int minDistance(string word1, string word2) {
        int length1 = word1.length(), length2 = word2.length();
        int memo[length2 + 1];
        for(int i = 0; i <= length2; i++)
            memo[i] = i;
        for(int i = 1; i <= length1; i++)
        {
            int pre = memo[0];
            memo[0] = i;
            for(int j = 1; j <= length2; j++)
            {
                int temp = memo[j];
                if(word1[i - 1] != word2[j - 1])
                    memo[j] = min(pre + 1, min(memo[j] + 1, memo[j - 1] + 1));
                else
                    memo[j] = pre;
                pre = temp;
            }
        }
        return memo[length2];
    }
};
